package model;

import java.util.ArrayList;
import java.util.Collections;

/**
 *
 * @author Alvin & Roy
 */
public class PathFinder{
        /** De lijst van knooppunten die al volledig onderzocht zijn */
	private ArrayList closed = new ArrayList();
	/** De lijst van knooppunten die nog niet volledig onderzocht zijn */
	private SortedList open = new SortedList();

	/** De map waarop gezocht wordt */
	private GameMap map;
	/** Het aantal zoekpogingen voordat er wordt opgegeven */
	private int maxSearchDistance;

	/** Alle knooppunten van de map */
	private Node[][] nodes;
	/** Is diagonaal bewegen toegestaan */
	private boolean allowDiagMovement;
	/** De heuristic die wordt gebruikt om te bepalen welk knooppunt het
            eerst onderzocht wordt*/
	private Heuristic heuristic;

        /**
	 * Constructor
	 *
	 * @param map De game map waarop gezocht wordt
	 * @param maxSearchDistance Het aantal stappen dat gezocht mag worden
         * voordat er opgegeven wordt
	 * @param allowDiagMovement Of er diagonaal bewogen mag worden
	 */
	public PathFinder(GameMap map, int maxSearchDistance, boolean allowDiagMovement) {
		this.heuristic = new Heuristic();
		this.map = map;
		this.maxSearchDistance = maxSearchDistance;
		this.allowDiagMovement = allowDiagMovement;

                //het aantal nodes is gelijk aan het aantal velden
                //ook staan ze in dezelfde volgorde
		nodes = new Node[map.getVelden().length][map.getVelden()[0].length];
		for (int x=0;x<nodes.length;x++) {
			for (int y=0;y<nodes[0].length;y++) {
				nodes[x][y] = new Node(x,y);
			}
		}
        }


	/**
	 * Bereken de kortste route
         * @param sx De huidige x locatie
         * @param sy De huidige y locatie
         * @param tx De x locatie van het doel
         * @param ty De y locatie van het doel
         * @return Als er een route gevonden wordt, wordt het pad gereturned
	 * Als er geen route gevonden wordt, wordt er null geruturned
         */
	public Path findPath(int sx, int sy, int tx, int ty) {
		// De begin status, de gesloten lijst is leeg en het enige
                // knooppunt in de open lijst is de huidige locatie, waarvan
                // de kosten 0 zijn. Dit omdat we ons daar al bevinden.
		nodes[sx][sy].cost = 0;
		nodes[sx][sy].depth = 0;
		closed.clear();
		open.clear();
		open.add(nodes[sx][sy]);
		nodes[tx][ty].parent = null;

		// Zolang we ons doel niet bereikt hebben en nog niet het
                // maximaal aantal zoekstappen hebben gezet
		int maxDepth = 0;
		while ((maxDepth < maxSearchDistance) && (open.size() != 0)) {
			// Haal het eerste knooppunt uit de open lijst, van dit
                        // knooppunt is het het meest waarschijnlijk dat het
                        // de goede richting is.
			Node current = getFirstInOpen();
			
                        // Als het doel bereikt is
                        if (current == nodes[tx][ty]) {
                            break;
			}

			removeFromOpen(current);
			addToClosed(current);

			// Zoek alle buren van het knooppunt af en onderzoek
			// of ze een mogelijke volgende stap kunnen zijn
			for (int x=-1;x<2;x++) {
				for (int y=-1;y<2;y++) {
					// Als het het huidige knooppunt is
					if ((x == 0) && (y == 0)) {
						continue;
					}

					// Als diagonaal bewegen niet toegestaan
					// is moet x of y 0 zijn
					if (!allowDiagMovement) {
						if ((x != 0) && (y != 0)) {
							continue;
						}
					}

					// bepaal de locatie van de buur
					int xp = x + current.x;
					int yp = y + current.y;

                                        boolean validLocation;
                                        if(Opties.getRanden()){
                                            validLocation = isValidLocation(sx,sy,xp,yp);
                                        }else{
                                             if(xp < 0){
                                                 xp = nodes.length-1;
                                             }else if(xp >= nodes.length){
                                                 xp = 0;
                                             }
                                             if(yp < 0){
                                                 yp  = nodes[0].length-1;
                                             }else if(yp >=nodes[0].length){
                                                 yp = 0;
                                             }
                                            validLocation = isValidLocation(sx,sy,xp,yp);
                                        }


                                        // als het een geldige locatie is
					if (validLocation) {
						// De koste van het buur knooppunt zijn de kosten van het huidige
                                                // knooppunt + de kosten van de beweging
						float nextStepCost = current.cost + getMovementCost(current.x, current.y, xp, yp);
						Node neighbour = nodes[xp][yp];
                                         
						// Als de nieuwe kosten lager liggen dan het van te voren was
                                                // controleer of deze niet weggegooid is.
                                                // Er is bepaald dat er een kortere weg is om bij het knooppunt
                                                // te komen dus moet het heronderzocht worden
						if (nextStepCost < neighbour.cost) {
							if (inOpenList(neighbour)) {
								removeFromOpen(neighbour);
							}
							if (inClosedList(neighbour)) {
								removeFromClosed(neighbour);
							}
						}

						// Als het knooppunt nog niet verwerkt en verwijderd is
                                                // worden de kosten gereset naar de huidige kosten en
                                                // wordt het knooppunt aan de lijst van mogelijke stappen
                                                // toegevoegd (open lijst)
						if (!inOpenList(neighbour) && !(inClosedList(neighbour))) {
							neighbour.cost = nextStepCost;
							neighbour.heuristic = getHeuristicCost(xp, yp, tx, ty);
							maxDepth = Math.max(maxDepth, neighbour.setParent(current));
							addToOpen(neighbour);
						}
					}
				}
			}
		}

		// Als er voor de target node geen parent is
		// betekend dat dat er geen pad was en wordt null gereturned
		if (nodes[tx][ty].parent == null) {
			return null;
		}

		// Maak een nieuw pad aan
                Path path = new Path();

                // Maak een node aan voor het doel
		Node target = nodes[tx][ty];

                // zolang het doel niet gelijk is aan de huidige locatie
		while (target != nodes[sx][sy]) {
                        //voeg de locatie van het doel toe aan de stappen
                        //let op: wordt aan de voorkant van de lijst ingevoerd
			path.prependStep(target.x, target.y);
                        //maak van de parent van het doel het nieuwe doel
			target = target.parent;
		}
                //voeg de huidige locatie als stap toe
		path.prependStep(sx,sy);

		// return het pad
		return path;
	}

	/**
	 * Haal het eerste element uit de open lijst. Dit is het volgende
         * element dat onderzocht wordt
	 *
	 * @return Het eerste element van de open lijst
	 */
	private Node getFirstInOpen() {
		return (Node) open.first();
	}

	/**
	 * Voeg een knooppunt toe aan de open lijst
	 *
	 * @param node Het knooppunt dat moet worden toegevoegd
	 */

	private void addToOpen(Node node) {
		open.add(node);
	}

	/**
	 * Controleer of een knooppunt in de open lijst voorkomt
	 *
	 * @param node Het knooppunt dat gecontroleerd wordt
	 * @return Staat het in de open lijst
	 */
	private boolean inOpenList(Node node) {
		return open.contains(node);
	}

	/**
	 * Verwijder een knooppunt uit de open lijst
	 *
	 * @param node Het knooppunt dat verwijderd moet worden
	 */
	private void removeFromOpen(Node node) {
		open.remove(node);
	}

	/**
	 * Voeg een knooppunt toe aan de gesloten lijst
	 *
	 * @param node Het knooppunt dat moet worden toegevoegd
	 */
	private void addToClosed(Node node) {
		closed.add(node);
	}

	/**
	 * Controleer of een knooppunt in de gesloten lijst voorkomt
	 *
	 * @param node Het knooppunt dat gecontroleerd moet worden
	 * @return Staat het in de lijst
	 */
	private boolean inClosedList(Node node) {
		return closed.contains(node);
	}

	/**
	 * Verwijder een knooppunt uit de gesloten lijst
	 *
	 * @param node Het knooppunt dat verwijderd moet worden
	 */
	private void removeFromClosed(Node node) {
		closed.remove(node);
	}

	/**
	 * Controleer of een knooppunt betreedbaar is
	 *
	 * @param sx De start x locatie
	 * @param sy De start y locatie
	 * @param x De x locatie die gecontroleerd wordt
	 * @param y De y locatie die gecontroleerd wordt
	 * @return Of de locatie betreedbaar is
	 */
	protected boolean isValidLocation(int sx, int sy, int x, int y) {
		boolean invalid = (x < 0) || (y < 0) || (x >= nodes.length) || (y >= nodes[0].length);

		if ((!invalid) && ((sx != x) || (sy != y))) {
                    Veld curVeld = map.getVeld(x,y);
                    invalid = (curVeld.getSpelObject() != null && !(curVeld.getSpelObject() instanceof Speler));
		}
		return !invalid;
	}

	/**
	 * Get the cost to move through a given location
	 *
	 * @param mover The entity that is being moved
	 * @param sx The x coordinate of the tile whose cost is being determined
	 * @param sy The y coordiante of the tile whose cost is being determined
	 * @param tx The x coordinate of the target location
	 * @param ty The y coordinate of the target location
	 * @return The cost of movement through the given tile
	 */
	public float getMovementCost(int sx, int sy, int tx, int ty) {
		return 1;
	}

	/**
	 * Get the heuristic cost for the given location. This determines in which
	 * order the locations are processed.
	 *
	 * @param mover The entity that is being moved
	 * @param x The x coordinate of the tile whose cost is being determined
	 * @param y The y coordiante of the tile whose cost is being determined
	 * @param tx The x coordinate of the target location
	 * @param ty The y coordinate of the target location
	 * @return The heuristic cost assigned to the tile
	 */
	public float getHeuristicCost(int x, int y, int tx, int ty) {
		return heuristic.getCost(x, y, tx, ty);
	}



        /**
	 * A single node in the search graph
	 */
	private class Node implements Comparable {
		/** The x coordinate of the node */
		private int x;
		/** The y coordinate of the node */
		private int y;
		/** The path cost for this node */
		private float cost;
		/** The parent of this node, how we reached it in the search */
		private Node parent;
		/** The heuristic cost of this node */
		private float heuristic;
		/** The search depth of this node */
		private int depth;

		/**
		 * Create a new node
		 *
		 * @param x The x coordinate of the node
		 * @param y The y coordinate of the node
		 */
		public Node(int x, int y) {
			this.x = x;
			this.y = y;
                }

		/**
		 * Set the parent of this node
		 *
		 * @param parent The parent node which lead us to this node
		 * @return The depth we have no reached in searching
		 */
		public int setParent(Node parent) {
			depth = parent.depth + 1;
			this.parent = parent;

			return depth;
		}

		/**
		 * @see Comparable#compareTo(Object)
		 */
		public int compareTo(Object other) {
			Node o = (Node) other;

			float f = heuristic + cost;
			float of = o.heuristic + o.cost;

			if (f < of) {
				return -1;
			} else if (f > of) {
				return 1;
			} else {
				return 0;
			}
		}
	}

        /**
	 * A simple sorted list
	 */
	private class SortedList {
		/** The list of elements */
		private ArrayList list = new ArrayList();

		/**
		 * Retrieve the first element from the list
		 *
		 * @return The first element from the list
		 */
		public Object first() {
			return list.get(0);
		}

		/**
		 * Empty the list
		 */
		public void clear() {
			list.clear();
		}

		/**
		 * Add an element to the list - causes sorting
		 *
		 * @param o The element to add
		 */
		public void add(Object o) {
			list.add(o);
			Collections.sort(list);
		}

		/**
		 * Remove an element from the list
		 *
		 * @param o The element to remove
		 */
		public void remove(Object o) {
			list.remove(o);
		}

		/**
		 * Get the number of elements in the list
		 *
		 * @return The number of element in the list
 		 */
		public int size() {
			return list.size();
		}

		/**
		 * Check if an element is in the list
		 *
		 * @param o The element to search for
		 * @return True if the element is in the list
		 */
		public boolean contains(Object o) {
			return list.contains(o);
		}
	}

    }
